The present invention relates to a VLSI microchip and method for real-time solution of seven types of partial differential equation encountered in most engineering and scientific applications. In particular, the present invention relates to the real-time solution of the following partial differential equations: Laplace equation, diffusion equation, wave equation, Poisson equation, modified diffusion equation, modified wave equation, and wave equation with damping.
Most engineering and scientific computing problems involve the solution of differential equations. In order to treat these problems by employing only the simple arithmetical operations available in digital systems, it is necessary to discretize the problem by numerical techniques. Typically, differential equation solutions are obtained by iteratively solving finite difference or finite element equations (the discrete counterpart to the continuous field equations). In the process, one of the prime advantages of digital computers is lost. So many individual operations are required in order to solve such problems, particularly field problems, that even though each individual step may take only a fraction of a microsecond, the complete solution may require many minutes or even hours. On an analog computer, however, the solution of a field problem becomes available almost immediately upon applying the desired boundary and initial conditions. An additional advantage of the analog computer is that a system capable of solving large problems may be implemented on a single VLSI chip or small set of chips, providing compact low-power components.
The field of analog computation attracted much attention in the fifties:
R. Tomovic and W. J. Karplus, High Speed Analog Computers. New York: John Wiley & Sons, 1962. PA1 W. J. Karplus and W. W. Soroka, Analog Methods. New York: McGraw-Hill, 1959. PA1 W. J. Karplus, Analog Simulation, Solution of Field Problems. New York: McGraw-Hill, 1958. PA1 G. Liebmann et al., "Solution of partial differential equations with resistance network analogue," British Journal of Applied Physics, vol. 1, no. 4, pp. 92-103, 1950. PA1 G. Liebmann et al., "Electrical analogues," British Journal of Applied Physics, vol. 4, pp. 193-200, 1953. PA1 W. J. Karplus et al., "The use of analog computers with resistance network analogues," British Journal of Applied Physics, vol. 6, pp. 356-357, 1955.
Although the basic concept was theoretically well proven at this time, it was of little practical use because of the many limitations of the implementations available in this pre-VLSI era. In spite of this, and the subsequent prevalent dominance of digital computers employing VLSI chips, analog computation has continued to be recognized as the ideal solution for applications where real-time processing is required.
The current status of analog VLSI technology makes it feasible to develop full-scale analog processing systems to aid conventional digital computers. Such analogy processors will provide assistance to conventional digital systems in problem areas well suited to analog solution, such as the solution of partial differential equations. These equations arise in most areas of engineering and scientific computing: gravitational, electrostatic, magnetic, thermal, stress, fluid flow field analysis, wave propagation, and image processing.
The present invention is a high-performance programmable VLSI chip for the analog solution of a family of partial differential equations commonly encountered in engineering and scientific computing. The present invention provides for the real-time solution of large linear and nonlinear partial differential equations and is fully compatible with existing digital systems. The present invention directly reduces the time and cost of solving differential equations by several orders of magnitude.
The present invention is also of a special purpose analog computer which is digitally reconfigurable. It has, in a very broad sense, a neural-like structure consisting of a large number of simple computational elements that are highly interconnected. For this reason it shares the characteristics of neural network systems: robustness and fault tolerance. Progress has been reported recently in the implementation of other types of analog computing systems using neural-like structures: 1) for the solution of nonlinear quadratic optimization problems; M. P. Kennedy and L. O. Chua, "Neural networks for nonlinear programming," IEEE Transactions on Circuits and Systems, vol. 35, no. 5, pp. 554-562, 1988; A. Rodriguez-Vazquez, R. Dominguez-Castro, A. Rueda, J. L. Huertas, and E. Sanchez-Sinencio, "Nonlinear switched capacitor neural networks for optimization problems," IEEE Transactions on Circuits and Systems, vol. 37, no. 3, pp. 384-398, 1988 and 2) for image processing applications using cellular neural networks; L. O. Chua and L. Yang, "Cellular neural networks: theory." IEEE Transactions on Circuits and Systems, vol. 35, no. 10. pp. 1257-1272, 1988; L. O. Chua and L. Yang, "Cellular neural networks: applications," IEEE Transactions on Circuits and Systems, vol. 35, no. 10, pp. 1273-1290, 1988; T. Matsumoto, L. O. Chua, and H. Suzuki, "Analog signal processing using cellular neural networks," Proc. IEEE ISCAS, pp. 958-961, New Orleans, La., 1990; L. Yang, L. O. Chua, and K. R. Krieg, "VLSI implementation of cellular neural networks," Proc. IEEE ISCAS, pp. 2425-2427, New Orleans, La., 1990. In spite of the fact that the solution of partial differential equations using analog computation techniques was an active area of research in the fifties, no systems have been implemented in analog VLSI circuitry for the solution of these type of equations.
The Laplace Equation EQU .gradient..sup.2 .phi.=0 (1)
is the most important and most commonly found fundamental equation of applied physics. It is useful in describing static and/or steady-state conditions in virtually all major areas of physics. Any field composed entirely of just one element type can be described by the Laplace equation (LE). One refers to three basic types of elements in a system: dissipative elements, potential energy storing elements and kinetic energy storing elements (in electric networks, these correspond to resistances, capacitors, and inductors, respectively). In all other areas of engineering there are elements that have similar functions, e.g. in mechanics the dissipative, potential energy storing, and kinetic energy storing elements correspond to dashpots, springs, and masses. Systems in which excitations are constant or enough time has elapsed since a previous change in the excitation took place are described by the LE. Systems containing only one of three basic types of elements occur in almost any physical area. Gravitational, electrostatic, and magnetic fields can be analyzed using the LE. Certain fluid-flow systems can also be analyzed using the LE, e.g. incompressible fluids flowing through mediums with very small pore channels are purely dissipative and can be modeled as resistive networks, and incompressible fluids flowing through open channels can be modeled as inductive networks. In mechanics, static deflection of elastic membranes having negligible masses can be modeled as capacitive networks. The irrotational steady-state of compressible or viscous liquids can be analyzed by means of the LE, as can temperature distribution in thermal systems in which static or steady-state conditions have been reached (not with time dependent excitations) and in which all energy reservoir elements have acquired all the energy they can store. Purely inductive 10 and capacitive 12 networks are modeled electronically using the same basic cell 14 shown in FIG. 1.
The transformation of a capacitive or an inductive network into a resistive network can be done using well known impedance transformations used in filter theory. A. S. Sedra and P. O. Bracket, Filter Theory and Design: Active and Passive, ch. 6 (Beaverton, Oreg.: Matrix Publishers, 1978). This takes place by scaling all elements in the network by the same factor. For example, by scaling all elements in a capacitive network by the s factor (complex frequency variable) they are transformed into equivalent resistances (R.sub.eq =1/C); the nodal voltages (and therefore the field solution they represent) are not affected by this operation. An inductive network scaled by 1/s is also transformed into a resistive network (R.sub.eq =L) without affecting the field solution. In the present invention resistors are simulated electronically by means of MOS transistors operating in non-saturated mode as described by R. L. Geiger, P. E. Allen, and N. R. Strader, VLSI Design Techniques for Analog and Digital Circuits, (New York: McGraw-Hill, 1990); J. Ramirez-Angulo, M. DeYong, S. Ming-Sheng, "CMOS cells for analog VLSI Laplace equation solver based on the resistive analogy method," Proc. IEEE Midwest Symposium on Circuits and Systems, in press, Washington, D.C., 1992. Analog VLSI electrical implementations of resistive networks have been used successfully for image processing, which is another area in which the LE frequently arises: H. Kobayashi, J. L. White, and A. A. Abidi, "An active resistor network for Gaussian filtering of images," IEEE Journal of Solid-State Circuits, vol. 26, no. 5, pp. 738-748, 1991.
The Diffusion or Conduction Equation ##EQU1## ranks with the LE as another important and fundamental equation of applied physics. Systems containing dissipative elements and one type of (kinetic or potential) energy storage element are described by the diffusion equation (DE). In these types of systems the field is dependent on time--now an additional variable--and the systems are characterized by solutions which approach their final value monotonically without overshoot. The LE may be considered a special case of the DE where sufficient time has elapsed since any previous change in the excitations, which causes the time dependent term of (2) to become zero.
The DE finds frequent application in heat-transfer problems where the systems under study consist of energy storage (capacitive) and dissipative elements; temperature and heat flux correspond to voltage and current in electric circuits. The DE describes the diffusion of any type of fluid particles in a space occupied by a different fluid. Concentration (.rho.) and flux (.psi.) of particles correspond in this case to V and I in electric circuits. Problems of irrotational incompressible fluid flow in which viscous (dissipative) and compressional forces (potential energy storage) occur, the DE is used to predict velocity potential or pressure at points within the flow stream. Skin effects in electromagnetics relate current density J along a conductor to its magnetic permeability (.mu.) and its electric conductivity (.sigma.). In general electromagnetics, Maxwell's equations reduce to the DE in fields that have conductivity but in which either the permeability or the dielectric constant can be neglected. Mechanical systems consisting of dashpot-type damping elements and either appreciable masses or spring-forces can be modeled using the DE. An example is the deflection of a string or a drumhead of negligible mass. Optics and soil compaction are other areas where the DE is fundamental.
In all cases, systems governed by the DE in two dimensions are modeled electronically by a grid of cells 20 and 22 as shown in FIG. 2a and FIG. 2b. Using the appropriate impedance transformations, the cell 22 of FIG. 2b is transformed into the cell 20 of FIG. 2a without changing the numerical value of the field solution. Parallel plate capacitors can be implemented in any double metal or double poly CMOS VLSI technology.
The Wave Equation ##EQU2## is the third fundamental equation of physics and describes the phenomenon of wave motion. Fields governed by the wave equation (WE) possess distributed inductances and capacitances (or the equivalent elements in other systems) and are modeled by cells 30 and 32 like the ones shown in FIG. 3b and FIG. 3c using transconductors, which can be replaced by MOS transistors in saturated mode. Scaling the network 32 in FIG. 3c by the factor s transforms the capacitors into resistors and the inductor into a "super-inductor" or frequency dependent negative resistance (FDNR1, characterized by an impedance Z=s.sup.2 K), as in the circuit 34 of FIG. 3a. Scaling the network 30 of FIG. 3b by the factor 1/s transforms the inductors into resistors and the capacitor into a "super-capacitor" or FDNR2 (characterized by an impedance Z=1/s.sup.2 D), as in the circuit 34 of FIG. 3a. Resistors are implemented electronically using MOS transistors in the non-saturated mode while "super-inductor" FDNRs use can be implemented using two capacitances and six MOS transistors operating in saturated mode. The "super-inductor" and "super-capacitor" both behave as FDNRs, but the former has a less complex CMOS VLSI implementation.
The WE is applicable to systems comprised of both types of energy storage elements with negligible dissipative characteristics. In dynamics pure wave motion occurs if appreciable spring-forces and inertial mass forces are present and only if viscous damping can be neglected. An example is the vibration of a drumhead with negligible damping. Vibrating strings may likewise exhibit these properties.
The Modified Equation Forms
The systems discussed above correspond to systems without internal excitations, where energy is supplied at the boundary. In various physical systems internal energy sources arise and the equations as well as grid elements representing these equations have to be modified to take these excitations into account. The excitations can be represented by means of current sources at each grid element as shown in FIG. 4 and in general they correspond to a transformation between different types of energy. For example, they might represent currents induced in a grid array of phototransitors by the incidence of light on their base regions. H. Kobayashi, J. L. White, and A. A. Abidi, "An active resistor network for Gaussian filtering of images," IEEE Journal of Solid-State Circuits, vol. 26, no. 5, pp. 738-748, 1991. The current sources are easily implemented electronically using MOS transistors in saturated mode. The inclusion of internal energy sources transforms the LE into the Poisson equation (PE): EQU .gradient..sup.2 .phi.=-ki.sub. i (4)
In a system governed by (4), in addition to the boundary conditions the internal source distribution i(x, y) must be specified. The PE finds a great deal of application in heat transfer systems in such areas as the analysis of thermal fields of nuclear reactors and dynamic systems in which viscous damping converts some of the mechanical energy into thermal energy. In electrostatics the presence of uniformly distributed charge throughout the field gives rise to the same equation.
The presence of distributed-energy sources in systems containing more than one type of element leads to equally simple modifications of the DE and WE (5) and (6), respectively: ##EQU3##
Equivalent circuit representations of the cells 14, 20, and 34 of FIG. 1, FIG. 2, and FIG. 3 are modified by including a current source i(x, y) injected to the cells 40, 42, and 44 node, as illustrated in FIG. 4. Internal energy sources can be time and position dependent and may also be a nonlinear function .function.(.phi.) of the potential existing at each point. For example, in a space charge limited vacuum tube the charge distribution is determined by the square root of the potential. The PE for this general case becomes: EQU .gradient..sup.2 .phi.=k.sub.1 i.sub.i -k.sub.2 .function.(.phi.)(7)
The DE and LE are modified accordingly to include additional terms -k.sub.3 .function.(.phi.). Electrical modeling of the function k.sub.3 .function.(.phi.) specific for each system can be done using nonlinear approximation techniques similar to those reported in E. Sanchez-Sinencio, J. Ramirez-Angulo, and B. Linares-Barranco, "OTA-based Nonlinear functions Synthesis," IEEE Journal of Solid State Circuits, vol. 24, no. 6, pp. 1576-1586, 1989.
Wave Equation with Damping
Many systems contain both types of energy-storage elements as well as dissipative elements. For their solution using analog VLSI circuits they can be represented by a grid of cells 50 like those shown in FIG. 5b. The cells can be impedance scaled by the factor 1/s to include floating resistors and capacitors and a grounded FDNR2 and a grounded capacitor as in the circuit 52 shown in FIG. 5a.
The electronic implementation of this cell uses MOS transistors in ohmic mode to simulate the floating resistors and poly-poly capacitors to implement both floating and grounded capacitors (care must be taken in connecting the bottom plate of the floating capacitors to the central cell-node so that the large bottom plate parasitic capacitance of the poly-poly capacitor is absorbed by the grounded capacitor and it does not introduce new elements into the cell). The wave equation, in this case called the damped wave equation, takes the form: ##EQU4##
Its modification to include distributed energy sources is done in a way similar to that explained before.
The response of a system described by (8) to a step-function excitation at a boundary is not monotonic as in the case of the DE, but may involve overshooting and oscillating about the equilibrium value since the eigen modes (poles) of the system are complex. The electronic implementation using transistors in saturated mode requires careful consideration of stability conditions since the gain available from active elements and the cell interconnections might result in positive feedback loops with a gain higher than one at some frequencies. Potentials and/or potential-gradients at every boundary must be specified, as well as kinetic and potential energy stored within the field at the initial instant.
The damped WE finds application in all the physical systems in which the three types of elements are present. Motion of points within systems containing appreciable mass, spring forces, and viscous damping is described by the damped WE. It also applies to the study of vibrating strings or elastic sheets, fluid-dynamic systems where the fluids are compressible and both viscous and inertial forces are present, and electromagnetic field problems for systems containing appreciable permeability, dielectric properties, and conductivity.